<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>欧拉一笔画</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="欧拉一笔画">欧拉一笔画</h1>
<p>这种eulur路径的算法就是要dfs, 并且 post-order</p>
<p><a href="https://www.cnblogs.com/acxblog/p/7390301.html">https://www.cnblogs.com/acxblog/p/7390301.html</a></p>
<h1 id="1-lc-332-reconstruct-itinerary">1. LC 332. Reconstruct Itinerary</h1>
<ul>
<li><a href="https://leetcode.com/problems/reconstruct-itinerary/">https://leetcode.com/problems/reconstruct-itinerary/</a></li>
</ul>
<p>Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.</p>
<p>Note:</p>
<p>If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [&quot;JFK&quot;, &quot;LGA&quot;] has a smaller lexical order than [&quot;JFK&quot;, &quot;LGB&quot;].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
One must use all the tickets once and only once.</p>
<pre><code><code><div>Example 1:
Input: [[&quot;MUC&quot;, &quot;LHR&quot;], [&quot;JFK&quot;, &quot;MUC&quot;], [&quot;SFO&quot;, &quot;SJC&quot;], [&quot;LHR&quot;, &quot;SFO&quot;]]
Output: [&quot;JFK&quot;, &quot;MUC&quot;, &quot;LHR&quot;, &quot;SFO&quot;, &quot;SJC&quot;]

Example 2:
Input: [[&quot;JFK&quot;,&quot;SFO&quot;],[&quot;JFK&quot;,&quot;ATL&quot;],[&quot;SFO&quot;,&quot;ATL&quot;],[&quot;ATL&quot;,&quot;JFK&quot;],[&quot;ATL&quot;,&quot;SFO&quot;]]
Output: [&quot;JFK&quot;,&quot;ATL&quot;,&quot;JFK&quot;,&quot;SFO&quot;,&quot;ATL&quot;,&quot;SFO&quot;]
Explanation: Another possible reconstruction is [&quot;JFK&quot;,&quot;SFO&quot;,&quot;ATL&quot;,&quot;JFK&quot;,&quot;ATL&quot;,&quot;SFO&quot;].
             But it is larger in lexical order.
</div></code></code></pre>
<h2 id="11-approach-1-backtracking--greedy">1.1  Approach 1: Backtracking + Greedy</h2>
<p>官方答案</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-string">"""  """</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findItinerary</span><span class="hljs-params">(self, tickets)</span>:</span>
        <span class="hljs-string">"""
        :type tickets: List[List[str]]
        :rtype: List[str]
        """</span>
        <span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict
        self.flightMap = defaultdict(list)

        <span class="hljs-keyword">for</span> ticket <span class="hljs-keyword">in</span> tickets:
            origin, dest = ticket[<span class="hljs-number">0</span>], ticket[<span class="hljs-number">1</span>]
            self.flightMap[origin].append(dest)

        self.visitBitmap = {}

        <span class="hljs-comment"># sort the itinerary based on the lexical order</span>
        <span class="hljs-keyword">for</span> origin, itinerary <span class="hljs-keyword">in</span> self.flightMap.items():
        <span class="hljs-comment"># Note that we could have multiple identical flights, i.e. same origin and destination.</span>
            itinerary.sort()
            self.visitBitmap[origin] = [<span class="hljs-literal">False</span>]*len(itinerary)

        self.flights = len(tickets)
        self.result = []
        route = [<span class="hljs-string">'JFK'</span>]
        self.backtracking(<span class="hljs-string">'JFK'</span>, route)

        <span class="hljs-keyword">return</span> self.result


    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">backtracking</span><span class="hljs-params">(self, origin, route)</span>:</span>
        <span class="hljs-keyword">if</span> len(route) == self.flights + <span class="hljs-number">1</span>:
            self.result = route
            <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>

        <span class="hljs-keyword">for</span> i, nextDest <span class="hljs-keyword">in</span> enumerate(self.flightMap[origin]):
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> self.visitBitmap[origin][i]:
                <span class="hljs-comment"># mark the visit before the next recursion</span>
                self.visitBitmap[origin][i] = <span class="hljs-literal">True</span>
                ret = self.backtracking(nextDest, route + [nextDest])
                self.visitBitmap[origin][i] = <span class="hljs-literal">False</span>
                <span class="hljs-keyword">if</span> ret:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>

        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
</div></code></pre>
<p>我的答案，原理是一样的</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findItinerary</span><span class="hljs-params">(self, tickets: List[List[str]])</span> -&gt; List[str]:</span>
        m = {}
        out = defaultdict(int)
        n = len(tickets)
        <span class="hljs-keyword">for</span> A, B <span class="hljs-keyword">in</span> tickets:        
            <span class="hljs-keyword">if</span> A <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> m:
                m[A] = [B]
            <span class="hljs-keyword">else</span>:
                nodes = m[A]
                pos = bisect.insort_left(nodes, B)
            
            out[A] = out[A] + <span class="hljs-number">1</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(cur, ans, num)</span>:</span>
            <span class="hljs-comment">#print(f"dfs() cur={cur} m={m} num={num}")</span>
            <span class="hljs-keyword">if</span> num == n+<span class="hljs-number">1</span>:
                <span class="hljs-keyword">return</span> ans
            <span class="hljs-keyword">if</span> cur <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> m:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>
            
            
            nodes = m[cur]
            nodes2 = nodes[:]
            <span class="hljs-keyword">for</span> node <span class="hljs-keyword">in</span> nodes2:
                m[cur].remove(node)
                r = dfs(node, ans+[node], num+<span class="hljs-number">1</span>)
                <span class="hljs-keyword">if</span> r:
                    <span class="hljs-keyword">return</span> r
                m[cur] = nodes2[:]
            <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>
        <span class="hljs-keyword">return</span> dfs(<span class="hljs-string">"JFK"</span>, [<span class="hljs-string">"JFK"</span>], <span class="hljs-number">1</span>)
                
</div></code></pre>
<h2 id="12-hierholzers-algorithm">1.2 Hierholzer's Algorithm</h2>
<p>In 1873, Hierholzer proposed an efficient algorithm to find the Eulerian cycle in linear time (\mathcal{O}(|E|)O(∣E∣)). One could find more details about the Hierholzer's algorithm in this course.</p>
<p>The basic idea of Hierholzer's algorithm is the stepwise construction of the Eulerian cycle by connecting disjunctive circles.</p>
<p>To be more specific, the algorithm consists of two steps:</p>
<ol>
<li>It starts with a random node and then follows an arbitrary unvisited edge to a neighbor. This step is repeated until one returns to the starting node. This yields a first circle in the graph.</li>
<li>If this circle covers all nodes it is an Eulerian cycle and the algorithm is finished. Otherwise, one chooses another node among the cycles' nodes with unvisited edges and constructs another circle, called subtour.</li>
</ol>
<p><img src="file:///e:\gitee\leetcode\graph\pics\332_eulerian_cycle.png" alt="332_eulerian_cycle.png"></p>
<p>By connecting all the circles in the above process, we build the Eulerian cycle at the end.</p>
<h3 id="eulerian-path">Eulerian Path</h3>
<p>To find the Eulerian path, inspired from the original Hierzolher's algorithm, we simply change one condition of loop, rather than stopping at the starting point, we stop at the vertex where we do not have any unvisited edges.</p>
<p>To summarize, the main idea to find the Eulerian path consists of two steps:</p>
<ol>
<li>Step 1). Starting from any vertex, we keep following the unused edges until we get stuck at certain vertex where we have no more unvisited outgoing edges.</li>
<li>Step 2). We then backtrack to the nearest neighbor vertex in the current path that has unused edges and we repeat the process until all the edges have been used.</li>
</ol>
<p>The first vertex that we got stuck at would be the end point of our Eulerian path. So if we follow all the stuck points backwards, we could reconstruct the Eulerian path at the end.</p>
<h3 id="algorithm">Algorithm</h3>
<p>Now let us get back to our itinerary reconstruction problem. As we know now, it is a problem of Eulerian path, except that we have a fixed starting point.</p>
<p>More importantly, as stated in the problem, the given input is guaranteed to have a solution. So we have one less issue to consider.</p>
<p>As a result, our final algorithm is a bit simpler than the above Eulerian path algorithm, without the backtracking step.</p>
<p>The essential step is that starting from the fixed starting vertex (airport 'JFK'), we keep following the ordered and unused edges (flights) until we get stuck at certain vertex where we have no more unvisited outgoing edges.</p>
<p>The point that we got stuck would be the last airport that we visit. And then we follow the visited vertex (airport) backwards, we would obtain the final itinerary.</p>
<p>Here are some sample implementations which are inspired from a thread of discussion in the forum.</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findItinerary</span><span class="hljs-params">(self, tickets)</span>:</span>
        <span class="hljs-string">"""
        :type tickets: List[List[str]]
        :rtype: List[str]
        """</span>
        <span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict
        self.flightMap = defaultdict(list)

        <span class="hljs-keyword">for</span> ticket <span class="hljs-keyword">in</span> tickets:
            origin, dest = ticket[<span class="hljs-number">0</span>], ticket[<span class="hljs-number">1</span>]
            self.flightMap[origin].append(dest)

        <span class="hljs-comment"># sort the itinerary based on the lexical order</span>
        <span class="hljs-keyword">for</span> origin, itinerary <span class="hljs-keyword">in</span> self.flightMap.items():
        <span class="hljs-comment"># Note that we could have multiple identical flights, i.e. same origin and destination.</span>
            itinerary.sort(reverse=<span class="hljs-literal">True</span>)

        self.result = []
        self.DFS(<span class="hljs-string">'JFK'</span>)

        <span class="hljs-comment"># reconstruct the route backwards</span>
        <span class="hljs-keyword">return</span> self.result[::<span class="hljs-number">-1</span>]

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">DFS</span><span class="hljs-params">(self, origin)</span>:</span>
        destList = self.flightMap[origin]
        <span class="hljs-keyword">while</span> destList:
            <span class="hljs-comment">#while we visit the edge, we trim it off from graph.</span>
            nextDest = destList.pop()
            self.DFS(nextDest)
        self.result.append(origin)
</div></code></pre>
<p>简洁版本</p>
<ul>
<li><a href="https://leetcode.com/problems/reconstruct-itinerary/discuss/78768/Short-Ruby-Python-Java-C%2B%2B">https://leetcode.com/problems/reconstruct-itinerary/discuss/78768/Short-Ruby-Python-Java-C%2B%2B</a></li>
</ul>
<p>(1)递归版本</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findItinerary</span><span class="hljs-params">(self, tickets)</span>:</span>
    targets = collections.defaultdict(list)
    <span class="hljs-keyword">for</span> a, b <span class="hljs-keyword">in</span> sorted(tickets)[::<span class="hljs-number">-1</span>]:
        targets[a] += b,
    route = []
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">visit</span><span class="hljs-params">(airport)</span>:</span>
        <span class="hljs-keyword">while</span> targets[airport]:
            visit(targets[airport].pop())
        route.append(airport)
    visit(<span class="hljs-string">'JFK'</span>)
    <span class="hljs-keyword">return</span> route[::<span class="hljs-number">-1</span>]
</div></code></pre>
<p>(2) Iterative version:</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findItinerary</span><span class="hljs-params">(self, tickets)</span>:</span>
    targets = collections.defaultdict(list)
    <span class="hljs-keyword">for</span> a, b <span class="hljs-keyword">in</span> sorted(tickets)[::<span class="hljs-number">-1</span>]:
        targets[a] += b,
    route, stack = [], [<span class="hljs-string">'JFK'</span>]
    <span class="hljs-keyword">while</span> stack:
        <span class="hljs-keyword">while</span> targets[stack[<span class="hljs-number">-1</span>]]:
            stack += targets[stack[<span class="hljs-number">-1</span>]].pop(),
        route += stack.pop(),
    <span class="hljs-keyword">return</span> route[::<span class="hljs-number">-1</span>]
</div></code></pre>
<h1 id="2-lc-753-cracking-the-safe">2. LC 753. Cracking the Safe</h1>
<p>There is a box protected by a password. The password is a sequence of n digits where each digit can be one of the first k digits 0, 1, ..., k-1.</p>
<p>While entering a password, the last n digits entered will automatically be matched against the correct password.</p>
<p>For example, assuming the correct password is &quot;345&quot;, if you type &quot;012345&quot;, the box will open because the correct password matches the suffix of the entered password.</p>
<p>Return any password of minimum length that is guaranteed to open the box at some point of entering it.</p>
<pre><code><code><div>Example 1:

Input: n = 1, k = 2
Output: &quot;01&quot;
Note: &quot;10&quot; will be accepted too.

Example 2:

Input: n = 2, k = 2
Output: &quot;00110&quot;
Note: &quot;01100&quot;, &quot;10011&quot;, &quot;11001&quot; will be accepted too.
 

Note:

n will be in the range [1, 4].
k will be in the range [1, 10].
k^n will be at most 4096.
</div></code></code></pre>
<h2 id="approach-1-hierholzers-algorithm-accepted">Approach #1: Hierholzer's Algorithm [Accepted]</h2>
<h3 id="intuition">Intuition</h3>
<p>We can think of this problem as the problem of finding an Euler path (a path visiting every edge exactly once) on the following graph: there are pow(k,n-1) nodes with each node having k edges.</p>
<p>For example, when k = 4, n = 3, the nodes are '00', '01', '02', ..., '32', '33' and each node has 4 edges '0', '1', '2', '3'. A node plus edge represents a complete edge and viewing that substring in our answer.</p>
<p>Any connected directed graph where all nodes have equal in-degree and out-degree has an Euler circuit (an Euler path ending where it started.) Because our graph is highly connected and symmetric, we should expect intuitively that taking any path greedily in some order will probably result in an Euler path.</p>
<p>This intuition is called Hierholzer's algorithm: whenever there is an Euler cycle, we can construct it greedily. The algorithm goes as follows:</p>
<p>Starting from a vertex u, we walk through (unwalked) edges until we get stuck. Because the in-degrees and out-degrees of each node are equal, we can only get stuck at u, which forms a cycle.</p>
<p>Now, for any node v we had visited that has unwalked edges, we start a new cycle from v with the same procedure as above, and then merge the cycles together to form a new cycle u \rightarrow \dots \rightarrow v \rightarrow \dots \rightarrow v \rightarrow \dots \rightarrow uu→⋯→v→⋯→v→⋯→u.</p>
<h3 id="algorithm-1">Algorithm</h3>
<p>We will modify our standard depth-first search: instead of keeping track of nodes, we keep track of (complete) edges: seen records if an edge has been visited.</p>
<p>Also, we'll need to visit in a sort of &quot;post-order&quot;, recording the answer after visiting the edge. This is to prevent getting stuck. For example, with k = 2, n = 2, we have the nodes '0', '1'. If we greedily visit complete edges '00', '01', '10', we will be stuck at the node '0' prematurely. However, if we visit in post-order, we'll end up visiting '00', '01', '11', '10' correctly.</p>
<p>In general, during our Hierholzer walk, we will record the results of other subcycles first, before recording the main cycle we started from, just as in our first description of the algorithm. Technically, we are recording backwards, as we exit the nodes.</p>
<p>For example, we will walk (in the &quot;original cycle&quot;) until we get stuck, then record the node as we exit. (Every edge walked is always marked immediately so that it can no longer be used.) Then in the penultimate node of our original cycle, we will do a Hierholzer walk and then record this node; then in the third-last node of our original cycle we will do a Hierholzer walk and then record this node, and so on.</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">crackSafe</span><span class="hljs-params">(self, n, k)</span>:</span>
        seen = set()
        ans = []
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(node)</span>:</span>
            <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> map(str, range(k)):
                nei = node + x          <span class="hljs-comment"># 代表着一条边</span>
                <span class="hljs-keyword">if</span> nei <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> seen:     <span class="hljs-comment"># 这条边还没被访问过</span>
                    seen.add(nei)       <span class="hljs-comment"># 标记这条边被访问过了</span>
                    dfs(nei[<span class="hljs-number">1</span>:])        <span class="hljs-comment"># dfs访问下一个节点</span>
                    ans.append(x)       <span class="hljs-comment"># 添加边到结果的字符串， 这里很关键，添加的动作必须放到dfs递归的后面， 就是前面说的”post-order”</span>

        dfs(<span class="hljs-string">"0"</span> * (n<span class="hljs-number">-1</span>))
        <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(ans) + <span class="hljs-string">"0"</span> * (n<span class="hljs-number">-1</span>)  <span class="hljs-comment"># 最后要加上初始节点”0”*(n-1), 因为我们的添加顺序是”post-order”, 所以这个初始节点放到了最后。</span>
</div></code></pre>
<p>注意看这里的解释 <a href="https://www.youtube.com/watch?v=iPLQgXUiU14">https://www.youtube.com/watch?v=iPLQgXUiU14</a></p>
<p>结合上面的视频， 写成下面的格式会更容易理解, 将哈密尔顿回路问题转换成了欧拉一笔画问题。 哈密尔顿</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">crackSafe</span><span class="hljs-params">(self, n: int, k: int)</span> -&gt; str:</span>
        start = <span class="hljs-string">"0"</span> * n
        ans = []
        seen = set()
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(node)</span>:</span>
            <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> map(str, range(k)):
                next_node = node[<span class="hljs-number">1</span>:]+x
                <span class="hljs-keyword">if</span> next_node <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> seen:
                    seen.add(next_node)
                    dfs(next_node)
                    <span class="hljs-comment">#print(f"node={node} next_node={next_node} x={x}")</span>
                    ans.append(x)
        dfs(start)
        <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>.join(ans) + <span class="hljs-string">"0"</span>*(n<span class="hljs-number">-1</span>)
</div></code></pre>

    </body>
    </html>